/**
问题：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例：

输入：[-2, 1, -3, 4, -1, 3, -5, 1, 2]
输出：6
解释：连续子数组 [4,-1, 3] 的和最大为 6。
**/


int maxSubArray(int[] nums) {
    int n = nums.length; if (0 == n) return 0;
    int[] dp = new int[n];
    for (int i = 0; i < n; i++) dp[i] = Integer.MIN_VALUE; // 初始化状态
    
    dp[0] = nums[0];

    int res = dp[0];
    for (int i = 1; i < n; i++) {
        dp[i] = Math.max(nums[i], dp[i-1] + nums[i]);
        res = Math.max(res, dp[i]);
    }

    return res;
}

/**
“最大子数组之和”这个问题来说，原问题的输入是包含负数的！
所以回到上面那个叙述：当窗口扩大的时候可能遇到负数，窗口中的值可能增加和减少，这种不确定性就已经限制了我们去使用滑动窗口：我们不知道什么时候该收缩左侧窗口，也就无法求出原问题的答案。
 */